A flow is a sequence of messages that share characteristics, including quality-of-service (QoS) properties. Network flows have to be regulated in order to ensure that the data transmissions conform to defined bandwidth limits.
One approach used to regulate network flow is the token bucket technique which is a common algorithm used to control the amount of data that is injected into a network, allowing for bursts of data to be sent. In general, the token bucket concept is based on an analogy of a bucket that contains tokens. The tokens represent a certain denomination related to data transmission, such as data packet size. Thus, using this analogy, when a data packet of a certain size is to be transmitted, the bucket is inspected to see if there are enough tokens in the bucket to cover that size data packet. If so, the appropriate number of tokens is removed from the bucket (also referred to as “cashing in the tokens”) and the data packet is transmitted. On the other hand, if an insufficient number of tokens is available, then transmittal of the data packet is canceled or held back until a sufficient number of tokens is available.
The token bucket concept is employed in several works. See, for example, U.S. Pat. No. 6,901,050 issued to Acharya, entitled “System and Methods for Flow-based Traffic Shaping,” (which describes a system with multiple token buckets, each handling its flow), U.S. Pat. No. 7,719,968 issued to Swenson et al., entitled “Multi-Priority Multi-Color Markers for Traffic Metering,” (which describes a system that contains token buckets with run time interdependencies), U.S. Pat. No. 7,586,848 issued to Gunduzhan, entitled “Elastic Traffic Marking for Multi-Priority Packet Streams in a Communications Network.” (which is a scheme based on token buckets that incorporates bandwidth loans), U.S. Pat. No. 6,862,265 issued to Appala et al., entitled “Weighted Fair Queuing Approximation in a Network Switch Using Weighted Round Robin and Token Bucket Filter,” (which combines weighted round robin scheduler with token bucket filters), and U.S. Pat. No. 6,147,970 issued to Troxel, entitled “Quality of Service Management for Aggregated Flows in a Network System,” (which incorporates two levels of token buckets with the goal of maximizing throughput).
These approaches however deal only with restricting data flows and do not take into consideration the content of the data. For instance, the situation may arise where an urgent message needs to be transmitted, but the respective token bucket is empty. With these conventional approaches there is a risk that the urgent message might not be transmitted.
Thus, improved techniques for regulating network data flows would be desirable.